# define _CRT_SECURE_NO_WARNINGS 1

#include "LevelOrder.h"

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}


void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (NULL == newnode)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->next = NULL;
    newnode->data = x;
    if (pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}


void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->tail);
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}


void QueueDestory(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}


QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->data;
}


QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->tail);
    return pq->tail->data;
}


bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}


int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QNode* cur = pq->head;
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}


void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (!root)
    {
        return;
    }
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%c ", front->data);
        if (front->left != NULL)
        {
            QueuePush(&q, front->left);
        }
        if (front->right != NULL)
        {
            QueuePush(&q, front->right);
        }
    }
    QueueDestory(&q);
}